Машина Минского

Машина Минского — многоленточная машина Тьюринга, у которой ленты слева не надстраиваются (ограничены по длине), все ячейки лент, за исключением самых левых, всегда пусты, а состояния самых левых ячеек постоянны. Также называется регистровая машина. Понятие ввёл в науку М. Минский

Система команд

Внешний алфавит (совокупность символов, записанных на лентах) машины Минского состоит из символов $0,1$. Символ пустого состояния $0$, все самые левые клетки всех лент находятся в состоянии $1$.

Полное описание $n$ — ленточной машины Минского задаётся указанием совокупности всех её внутренних состояний $q_{i},\ i=1,\dots ,n$ и программы машины, состоящей из команд вида

$q_{i}a_{1}\dots a_{s}\to q_{\alpha }T_{\alpha _{1}}\dots T_{\alpha _{s}},$

где $i=1,\dots ,n$; $a_{\lambda }=0,1$; $\alpha =0,1,\dots ,n$; $\alpha _{\lambda }=0,1,-1$.

Эти команды означают, что, находясь во внутреннем состоянии $q_{i}$ и воспринимая ячейки лент в состояниях $a_{1}\dots a_{s}$, машина заменяет $q_{i}$ на $q_{\alpha }$, после чего сдвигает ленты в направлениях $T_{\alpha _{1}}\dots T_{\alpha _{s}}$ ($T_{-1},T_{1},T_{0}$ означают соответственно сдвиг ленты на одну ячейку влево, вправо и оставление ленты неподвижной).

Так как $1$ есть состояние самой левой ячейки, то в командах из $a_{\lambda }=1$ должно следовать неравенство $\alpha _{\lambda }\neq -1$.

Свойства

• Для каждой частично рекурсивной функции $f(x)$ существует трёхленточная машина Минского, вычисляющая эту функцию, то есть переходящая из конфигурации ${10}^{x-1}q_{1}0q_{1}1q_{1}1$ в конфигурацию ${10}^{f(x)-1}q_{0}0q_{0}1q_{0}1$, если $f(x)$ определено, и работающая вечно, если $f(x)$ не определено.
• Для каждой частично рекурсивной функции $f(x)$ существует двухленточная машина Минского, которая для любого натурального $x$ перерабатывает число $2^{x}$ в число $2^{f(x)}$, если $f(x)$ определено, и работающая безостановочно, не переходя в заключительное внутреннее состояние $q_{0}$, если $f(x)$ не определено
• Для каждой частично рекурсивной функции $f(x)$ существует операторный алгоритм, перерабатывающий $2^{2^{x}}$ в $2^{2^{f(x)}}$, программа которого состоит лишь из приказов вида{{pb

  ${\overline {\underline {|\,{\times 2}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 3}\,|\,\alpha \,|}}},{\overline {\underline {|\,{\times 2}\,|\,\alpha \,|\,\beta \,|}}}.$

Регистровая машина

Регистровая (или программная) машина состоит из конечного числа регистров, хранящих неотрицательные целые числа и управляющий программный блок, который выполняет операции над содержимым регистров согласно программе (упорядоченной последовательности команд). Команды содержат сведения о выполняемой операции, регистре, номерах одной или двух других команд.

Для всякой машины Тьюринга всегда можно построить эквивалентную ей регистровую машину, использующую два регистра и выполняющую четыре операции:

• ${\underline {\overline {|\,a^{0}\,|}}}$ — занести $0$ в регистр $a$;
• ${\underline {\overline {|\,a'\,|}}}$ — добавить $1$ к содержимому регистра $a$ и перейти к новой команде;
• ${\underline {\overline {|\,a^{-}(n)\,|}}}$ — вычесть $1$ из содержимого регистра $a$ и перейти к следующей команде или перейти к команде $n,$ если в нём уже содержится $0$;
• ${\underline {\overline {|\,n\,|}}}$ — перейти к команде $n$.

Двухленточная машина Минского полностью эквивалентна регистровой машине с двумя регистрами. Если длины лент от считывающих головок до концов рассматривать как представления чисел $m$ и $n$, операции $m^{+}$ и $n^{+}$ сдвигают головки в сторону от концов, а $m^{-}$ и $n^{-}$ к концам, при условии, что не достигнут конец ленты, полностью эквивалентна регистровой (программной) машине с двумя регистрами, в один из регистров которой помещается нуль, а в другой число $2^{a}3^{m}5^{n}$.

См. также

• Машина Тьюринга
• Операторный алгоритм

Литература

• Минский М. Вычисления и автоматы. — М.: Мир, 1971. — 360 с.